from typing import List

class Solution:
    """
    方法：二分查找
    在旋转排序数组中查找目标值。通过比较中间元素与最后一个元素的大小关系来判断目标值在哪一侧。
    如果中间元素大于最后一个元素，说明该元素在旋转点左侧；否则在右侧。
    然后根据目标值与最后一个元素的大小关系，判断目标值应该在哪一侧。

    Args:
        nums: List[int], 旋转排序数组
        target: int, 要查找的目标值

    Returns:
        int: 如果找到目标值返回其索引，否则返回-1

    Time: O(logn)，其中n是数组的长度，每次将搜索范围缩小一半
    
    Space: O(1)，只使用常数额外空间
    """
    def search(self, nums: List[int], target: int) -> int:
        def check(i: int) -> bool:
            x = nums[i]
            if x > nums[-1]:
                return target > nums[-1] and x >= target
            return target > nums[-1] or x >= target
        left, right = -1, len(nums) -1 #(-1, n-1)
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid 
        return right if nums[right] == target else -1
        

    """
    方法：二分查找
    在旋转排序数组中查找目标值。通过比较中间元素与数组首元素的大小关系来判断目标值在哪一侧。
    如果中间元素大于等于首元素，说明左半部分有序；否则右半部分有序。
    然后判断目标值是否在有序部分的范围内来决定搜索区间。

    Args:
        nums: List[int], 旋转排序数组
        target: int, 要查找的目标值

    Returns:
        int: 如果找到目标值返回其索引，否则返回-1

    Time: O(logn)，其中n是数组的长度，每次将搜索范围缩小一半
    
    Space: O(1)，只使用常数额外空间
    """
    def search1(self, nums, target):
        left, right = 0,  len(nums) - 1
        while(left <= right):
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums [-1]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1